For each possible subarray we compute the sum and store the maximum

brute_force(a[])
	n = a.length()
	max = Integer.MIN_VALUE
	for i = 0 to n
		sum = 0
		for j = i to n
			sum += a[j]
			if sum > max
				max = sum
	return max
Copy

Kadane's algorithm is based on two properties of the subarray with maximum sum:

1. sum of values in any prefix of the optimal subarray is positive. By contradiction, remove a negative prefix to get a subarray with a larger sum
2. the value that precede the first value of the optimal subarray is negative. By contradiction, include this positive value to get a subarray with a larger sum

To solve the problem we use Kadane's algorithm:

kadane_algorithm(a[])
	n = a.length()
	max = Integer.MIN_VALUE
	sum = 0

	for i = 0 to n
		if sum > 0 // property 1)
			sum += arr[i]
		else // property 2)
			sum = arr[i]

		max = Math.max(sum, max)

	return max
Copy

Traverse every array element and find the highest bars on the left and right sides.
Take the smaller of two heights.
The difference between the smaller height and the height of the current element is the amount of water that can be stored in this array element.

The point is to think locally, not globally.
We can compute the left and right leaders.

An element of array is a right leader if it is greater than or equal to all the elements to its right side. The rightmost element is always a leader.

Given the array of heights, we use two arrays to store the right and left leaders:

Now, how many units of water we can find on top of the cell ?
The minimum height between the left and right leader of the current position minus , the height of the current position:

The idea is taken from the Precomputation solution, where we only use two variables to store the currently "meaningful" leaders.

We take two pointers, left and right and we initialize left to 0 and right to the last index n-1.
We also create two variables, left_max and right_max, they represent the maximum left/right height seen so far.

Since left is the first left_max is 0, same for right_max.
This is intuitive: we can't store water in the first and last column.

Now we iterate, as long left < right.
We have to decide which pointer we have to shift: we shift the pointer that has smaller height value:

• if heights[left] < heights[right] we shift left
• we shift right otherwise

Now, if we have that heights[left] > left_max we can't store any water over the position pointed by left, it would fall as left_max is not high enough.

Otherwise we compute the amount of water stored in left, as always with left_max - heights[left]. Then we finally shift left by 1.
The reasoning with the right pointer is the same.

The following pseudo-code solves the problem

max_water(heights[]) 
	n = heights.length()
	result = 0
	left = 0
	right = n-1

	left_max = 0 // max height seen by "left" so far
	right_max = 0 // max height seen by "right" so far

	while left < right 
		if heights[left] < heights[right] // shift "left"
			if heights[left] > left_max 
				left_max = heigths[left] // cant store water
			else 
				result += left_max - heights[left]
			left += 1
		else // shift right
			if heights[right] > right_max 
				right_max = heights[right] // cant store water
			else 
				result += right_max - heights[right]
			right -= 1

	return result
Copy

An efficient algorithm that searches for a given key within a sorted array of items.
Binary search repeatedly divides the search range in half until the target element is found or the search range becomes empty, resulting in a time complexity of

Binary search is a technique that falls under the umbrella of the divide-and-conquer paradigm, that tackles a complex problem by breaking it down into smaller, more manageable subproblems of the same type:

• divide: the initial problem instance is partitioned into smaller subinstances of the same problem
• solve: these subinstances are then solved recursively. If a subinstance reaches a certain manageable size, a straightforward approach is employed to solve it directly
• combine: the solutions obtained from the subinstances are combined to obtain the final solution for the original, larger instance of the problem

Considering the binary search, we have:

• divide: the array is divided into two roughly equal halves, centering around the middle element of the array
• solve: compare the middle element of the array with the searched key. If the middle element is a match, the search stop successfully. If not, we recursively search for the key only in one of the two halves that may contain the key, based on whether the desired key is greater or lesser than the middle element
• combine: there is nothing to combine

It is also important to observe that when there are multiple occurrences of the searched key, the function returns the position of the first encountered occurrence, not necessarily the first occurrence in the vector.
However, it is often very useful to report the position of the first (or last) occurrence of the searched key.

We can obtain this behavior with the following pseudo-implementation.

binary_search(a[], target) 
	n = a.length()
	low = 0
	high = n - 1
	answer = -1

	while low < high
		// (low + high)/2 might overflow if (high+low) is very big
		middle = low + (high - low) / 2

		if a[middle] == target
			answer = middle
			high = middle
		else if a[middle] < target
			low = middle
		else 
			high = middle

	return answer
Copy

In this implementation, when a match is found, we do not immediately return its position. Instead, we update the answer variable and set high to the position of this occurrence.
This way, we continue the search in the first half of the array, seeking additional occurrences of the key.
If there are more matches, answer will be further updated with smaller positions.

We can use the binary search philosophy to solve the problem.
We compute the middle of the array.
If the element in the middle is smaller than its right neighbor than the right neighbor could be a leader, and we do low = mid + 1 to proceed the search in the right side of the array.
Otherwise we do the opposite.

peak_elements(a[])
	n = a.length()
	low = 0
	right = n - 1

	while low < high
		mid = low + (high - low) / 2

		if a[mid] < a[mid + 1]
			low = mid + 1
		else 
			right = mid 

	return low 
Copy

This solution works because a leader is guaranteed to be found (as a last resource, in the first or last element of the array).
The beauty of this solution is that it naturally covers all the strange cases.
It would be tempting to write something like

if a[mid] > a[mid+1] && a[mid] > a[mid-1]
	return mid
Copy

but that requires to cover many edge cases (array of size 1, 2, if mid is , if mid is , ...)

Tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once.
Such traversals are classified by the order in which the nodes are visited.

Traversing a tree involves iterating over all nodes in some manner.
Because from a given node there is more than one possible next node some nodes must be deferred, aka stored, in some way for later visiting.
This is often done via a stack (LIFO) or queue (FIFO).
As a tree is a recursively defined data structure, traversal can be defined by recursion.
In these cases the deferred nodes are stored implicitly in the call stack.

Depth-first search is easily implemented via a stack, including recursively (via the call stack), while breadth-first search is easily implemented via a queue.

A simple solution is to traverse the tree and do following for every traversed node :

1. Find maximum sum from-leaf-to-root in left subtree of
2. Find maximum sum from-leaf-to-root in right subtree of . 
3. Add the above two calculated values and and compare the sum with the maximum value obtained so far and update the maximum value. 
4. Return the maximum value.

Max Sum leaf-to-root path in a Binary Tree:
Given a Binary Tree, find the maximum sum path from a leaf to root.
For example, in the following tree, there are three leaf to root paths:

• 8 -> -2 -> 10
• -4 -> -2 -> 10
• 7 -> 10.

The sums of these three paths are 16, 4 and 17 respectively.
The maximum of them is 17 and the path for maximum is 7 -> 10.

					              10  
				                 /  \  
				               -2    7  
				              /  \       
				             8   -4
Copy

Solution:

1. First find the leaf node that is on the maximum sum path.
2. Once we have the target leaf node, we can print the maximum sum path by traversing the tree.

Here we provide a Java pseudo-implementation of the problem:

maxValue = 0
targetLeaf = null

maxLeafRootSum(root)
	targetLeaf = findTargetLeaf(root, 0)
	print(maxValue)

// set targetLeaf to the leaf with maximum sum path to root
findTargetLeaf(node, currMaxValue) 
	if root == null
		return 

	// hold the sum of nodes on path from root to this node
	currMaxValue += node.value

	// leaf and the path to this has maximum sum: set targetLeaf
	if node.isLeaf 
		if currMaxValue > maxValue
			maxValue = currMaxValue
			targetLeaf = node

	// this is not a leaf node: recur down to find targetLeaf
	findTargetLeaf(node.left, currMaxValue)
	findTargetLeaf(node.right, currMaxValue)
Copy

So, the trivial solution of Maximum Path Sum works as follows:

• For every node we compute:
  • the maximum path sum from to a leaf,
  • the maximum path sum from to a leaf,
  • we take the maximum between the two
  • we sum the value of X
  • if the sum is greater than the current maximum we update the current maximum

For every node we call twice maxLeafRootSum, which costs O(n), hence the total cost is O(n^2)

We can find the maximum sum using single traversal of binary tree.
The idea is to maintain two values in recursive calls

1. Maximum root-to-leaf path sum for the subtrees rooted under current node. 
2. The maximum path sum between leaves (desired output).

For every visited node , we find the maximum root-to-leaf sum in left and right subtrees of . We add the two values with , and compare the sum with maximum path sum found so far.

As before, here a pseudo-code implementation:

maxValue = 0

// calculates two things:
// 1) maximum path sum between two leaves, which is stored in maxValue.
// 2) maximum root-to-leaf path sum, which is returned.
maxPathSum(root)
	if root == null
		return 0

	left = maxPathSum(root.left)
	right = maxPathSum(root.right)
	
	maxValue = Math.max(maxValue, left + right + root.value)

	return left + right + root.value
Copy

In "one pass" (aka one traversal) we do what we did in the trivial solution.
The reasoning is the following:

• take a node
• compute the max sum path from to a leaf and the max sum path from to a leaf .
• the sum path from to (passing by ) is greater than the one previously stored? then we update the max

The result is maxValue when the program terminates.

The naive approach is obvious and takes O(n^2), we simply scan the array and we return when we find two numbers that adds up to X.

existsPairSum(a[], x)
	n = a.length()
	for i = 0 to n
		for j = i+1 to n
			if a[i] + a[j] == x
				return true
			if a[i] + a[j] > x
				break // a is sorted, need a new "i"
	return false
Copy

Two pointers is really an easy and effective technique that is typically used for searching pairs in a sorted array.
It employs using two pointer, typically one from the start of the array going left-to-right and one from the end of the array going right-to-left, until they meet.
We already seen a sneak peak of this in Trapping Rain Water.

We take two pointers, one representing the first element and other representing the last element of the array, and then we add the values kept at both the pointers.

If their sum is smaller than X then we shift the left pointer to right or if their sum is greater than X then we shift the right pointer to left, in order to get closer to the sum.
We keep moving the pointers until we get the sum as X.

existsPairSum(a[], x)
	n = a.length()
	left = 0
	right = n-1

	while left < right
		if a[left] + a[right] == x
			return true
		if a[left] + a[right] < x
			left += 1 // smaller than target, we need to increase
		else
			right -= 1 // bigger than target, we need to decrease

	return false
Copy

A binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree.
The time complexity of operations on the binary search tree is linear with respect to the height of the tree.

Binary search trees allow binary search for fast lookup, addition, and removal of data items.
Since the nodes in a BST are laid out so that each comparison skips about half of the remaining tree, the lookup performance is proportional to that of binary logarithm.

The complexity analysis of BST shows that, on average, the insert, delete and search takes for n nodes.
In the worst case, they degrade to that of a singly linked list:

We store the position of the frogs in a BST, frogBST.
When a mosquito lands on a position we check which frog will eat it by simply doing a frogBST.predecessor(b) query on the tree.
It is possible that some mosquito cannot be eaten right away, the uneaten mosquito will be stored in their own BST (mosquitoBST), using their landing position as keys.

There is no need to sort anything.

The algorithm behaves as follows:

• insert the frogs, by their order, in a BST frogBST using their position as key
• for each mosquito m in mosquitoes
  - find the predecessor f of m in frogBST, if f.position + f.tongue >= m.position
  - f eats the mosquito m and its tongue grows by the size of m
  - maybe f now can eat other mosquitoes that could not be eaten before, inspect mosquitoBST to see if there is a mosquito that f can eat, and in case repeat.
  - inspect: find the successor m' of f.position in mosquitoBST and see if f.position + f.tongue >= m'.position
  - f now may overlap or fully contain other frogs
  - For every successor of f in frogBST:
  - if it overlaps with f remove the overlap by updating their positions
  - position of the successor = f.position + f.tongue + 1
  - if it is fully contained by f then delete this frog as it will never eat
  - else, insert m in mosquitoBST and continue
  

Time Complexity:

• Each predecessor query on the frog tree can be answered in time.
• Each successor query of the mosquito tree can be answered in time.
• Forcing no overlaps: we can "move/shift" frogs at most for every mosquito that is eaten, then

The Sweep Line Algorithm is an algorithmic paradigm used to solve a lot of problems in computational geometry efficiently.
The sweep line algorithm can be used to solve problems on a line or on a plane.

The sweep and line algorithm use an imaginary vertical line sweeping over the x-axis.
As it progresses, we maintain a running solution to the problem at hand.
The solution is updated when the vertical line reaches a certain key points where some event happen. The type of the event tells us how to update the solution.

Let's apply the sweep and line algorithm to the problem above.
We let the sweep line from left to right and stop at the beginning or at the end of every interval.
These are the important points at which an event occurs: interval start or end.
We also maintain a counter which keeps track of the number of intervals that are currently intersecting the sweep line, along with the maximum value reached by the counter so far.

For each point we first add to the counter the number of intervals that begin at that point, and then we subtract the number of intervals that end at that point.
The figure below shows the points touched by the sweep line and the values of the counter:

Observation: The sweep line only touches points on the x-axis where an event occurs.
This is important because the number of considered points, and thus the time complexity, is proportional to the number of intervals, and not to the size of the x-axis.

The following is the intuitive solution.
It has two nested loops, one that iterates right-left times and the inner one that iterates times, where is the number of ranges.
The complexity then is time.

isCovered(ranges, left, right) 
	for i = left to right 
		covered = false // i is not covered until proven otherwise
		for range in ranges 
			if i >= range.start && i <= range.end 
				covered = true // i is covered by the current interval
				break;
			
		// if i is not covered then we return false
		if covered == false 
			return false
	
	// each i in [left, right] is covered by at least one range
	return true;
Copy

To solve the problem more efficiently we use sweep line and a map.
The complexity is linear in the maximum between the number of ranges and right

isCovered(ranges, left, right)
	// map: point i -> number of open ranges in i
	HashMap openRangesAt; 
	for range in ranges 
		openRangesAt.insert(openRangesAt.getOrDefault(range.start, 0) + 1)
		// range.end+1 as the ranges are inclusive!
		openRangesAt.insert(openRangesAt.getOrDefault(range.end+1, 0) + 1)
	

	openRangesNow = 0
	for i = 0 to left 
		openRangesNow += openRangesNow.getOrDefault(i, 0)

	for point=left to right 
		openRangesNow += openRangesNow.getOrDefault(point, 0)
		if openRangesNow == false
			return false

	return true
Copy

We use the sliding window approach: the implementation is self-explanatory

longestKGoodSegment(array, k)
	n = array.length()
	if k == 0 || n == 0
		return (-1,-1)
	if k == 1
		return (0,0)

	wSize = 1 // current window size
	left, right = 0 // left and right delimiter of the window
	pointer = 1 // always points to the element just outside the window

	maxWSize = 1 // store the maximum size of the window so far
	leftResult, rightResult = 0 // delimiter of the maximum window

	HashSet distincts // store distinct elements in the window
	distincts.insert(array[0]) // the windows starts with the first element

	while pointer != n // proceed until the pointer is outside the array
		// the element just outside the window is to be included
		if Math.abs(array[right], array[pointer]) == 1
			distincts.insert(array[pointer]);
			right ++ 1 // stretch the window
			wSize ++ 1 // the size of the window grows
			pointer ++ 1 // shift the pointer to be outside of the window
			
			if wSize > maxWSize // the new size is the maximum?
				maxWSize = wSize
				leftResult = left
				rightResult = right 

				if distincts.size() == k // the window contains k distinct?
					return (leftResult, rightResult)
		else 
			left = pointer // shift the window: the start becomes pointer
			right = left // the window is made of one element
			w_size = 1 
			pointer = right+1 // points to the element outside the window
			distincts.clear() // reset the distinct elements in the window

	return (-1,-1)
Copy

The obvious brute force approach: from each element we compute every possible subarray starting in that element, check if sum is a multiple of k and store the maximum length so far.

Prefix sums, also known as cumulative sums or cumulative frequencies, offer an elegant and efficient way to solve a wide range of problems that involve querying cumulative information about a sequence of values or elements.

The essence of prefix sums lies in transforming a given array of values into another array, where each element at a given index represents the cumulative sum of all preceding elements in the original array.

An example of prefix sum array is shown in the picture:

Where it is clear that

The solution is based on the following mathematical property:
Observation: any two prefix sums that are not next to each other with the same mod k, or a prefix sum with mod k = 0 that is not the first number will yield a valid subarray.

checkSubarraySum(array, k)
	n = array.length()
	
	prefixSumArray[] // prefix sum array
	pS = 0
	for i = 0 to n 
		pS += array[i]
		prefixSumArray[i] = pS

	// map: modulo -> index i st prefixSumArray[i] % k = modulo
	HashMap modsToIndices
	for (i, prefixSum) in array.enumerate() 
		modulo = prefixSum % k

		if modulo == 0 && i != 0 // if modulo is 0 and not the first ok
			return true

		// first time we see this modulo
		if modsToIndices.contains(modulo) == false
			modsToIndices.insert(modulo, i)
		else 
			// this modulo has been seen
			previousIndex = modsToIndices.get(modulo);
			if previousIndex < i - 1
				return true

	return false
Copy

Observation:
We really do not need a full prefix sum array, it is enough to compute sum as we go and use it also as the mod result (we make sum = sum%k and use it as key, sums in modulo works). This is true because we never use the prefix sum of an element before the predecessor, so we can store only the sum up until now.

The Fenwick Tree, also known as the Binary Indexed Tree (BIT), is a data structure that maintains the prefix sums of a dynamic array.
With this data structure we can update values in the original array and still answer prefix sum queries.
Both operations runs in logarithmic time.

Consider the following problem: we have an array A[1..n] of integers and we would like to support the following operations:

• sum(i) returns the sum of the elements in A[1...i]
• add(i,v) adds the value v to the entry A[i]

We have two trivial solutions:

• Store A as it is. This way, sum(i) is solved by scanning the array in time, and add(i,v) is solved in
• Store the prefix sums of A. This way sum(i) is solved in and add(i,v) is solved modifying all the entries from i to n in time.

The sum/add query time trade-offs of these solutions are unsatisfactory

The Fenwick Tree provides better tradeoffs for this problem.
The Fenwick tree efficiently handles these queries in while using linear space.
In fact the Fenwick tree is an implicit data structure, which means it requires only additional space to the space needed to store the input data, in our case the array A

In our description, we will gradually introduce this data structure by constructing it level by level.

We use the following 1-indexed array in our example:

We start with a simpler version of the problem: we focus on solving sum queries only for positions that are powers of 2, positions 1, 2, 4, 8 in A.
The solution of this simplified version, shown in the picture, will be the first level of the Fenwick Tree

We notice that:

• there is a fictitious root node named 0 (the array is 1-indexed, the root is a dummy as it is an out-of-bound node)
• over every node there is the corresponding index in A
• the value of every node is the prefix sum up to that index
• under every node we have a range of integers: those are the positions covered by that node

With this solution we have that:

• sum(i) query: straightforward, we simply access the node i, provided that i is a power of 2
• add(i,v) query: we need to add v to all the nodes that covers ranges that include the position i, for example if we want to do add(3,10) we need to add 10 to the nodes 4 (as it has range and ) and 8 (as it has range and ).
  • general rule add(i,v): find the smallest power of 2 grater than i, let's call it j, and we add v to the nodes j, j*2, j*(2^2), ... (j is the index in the original array, stored over every node in the picture above)

We observe that sum takes constant time and add takes time.
This is very good, can we extend this solution to support sum queries on more positions?

Observation: currently we are not supporting queries for positions within the ranges between consecutive powers of 2.
Look at the image above: positions that falls in the range (subarray) [5, 7], which falls between the indices () and (), are not supported.
In fact we can't make the query sum(5).
Enabling queries for this subarray is a smaller instance of our original problem.

We can apply the same strategy by adding a new level to our tree.
The children of a node stores the partial sums starting from the next element.
The emphasis is in starting.

If the subarray is A[l..r], the new level will support the sum(i) query for any i such that i-l+1 is a power of 2.

Lemma: our two-level tree can now handle sum(i) queries for positions that are the sum of two powers of 2.
Proof:

• Consider a position i expressed as , where .
• We can decompose the range into two subranges:
• Both of these two subranges are covered by nodes in our tree
  - the range is covered by the node at the first level
  - the range is covered by the node i at the second level
  Example: intuition on how to compute sum(5)
• the range is divided in two subranges
  • , covered by the node 4
  • , covered by the node 5
• the result, which is 16, is obtained by summing the values of the nodes
  • search the node 4 in the tree: it is at the first level as it is a power of 2
  • take its value, which is 9
  • search the node 5
    • it is not a power of two but a sum of power of 2, hence it is at the second level
    • the biggest power of 2 smaller than 5 is 4, hence the node 5 is a children of the node 4
    • take its value, which is 7
  • 9 + 7 = 16

Which are the position still not supported? The positions that are neither a power of 2 or the sum of two powers of 2.
In our example, we can't compute sum(7) as 7 is either of those.
To support this we add a new level to our tree, so we can support positions that are sum of three powers of 2

Example: intuition on how to compute sum(7)

• the position can be expressed with , with , where:
• in fact we have that
• the range can be divided in three subranges:
• and we have that
  • the first subrange is covered by the node 4, which has value = 9
  • the second subrange is covered by the node 6, which has value = 4
  • the third subrange is covered by the node 7, which has value = 2
• the biggest power of 2 smaller than 7 is 4, hence all the useful nodes will be in the subtree rooted in the node 4
  • 4 is a power of 2, first level
  • 6 is the sum of two power of 2, second level
  • 7 is the sum of three power of 2, third level
• 9 + 4 + 5 = 15, which is sum(7)

And we are done, this is the Fenwick tree of the array A.
We can make some observations:

1. While we have represented our solution as a tree, it cal also be represented as an array of size n+1, as shown in the figure above
2. We no longer require the original array A because any of its entries A[i] can be simply obtained by doing sum(i) - sum(i-1). This is why the Fenwick tree is an implicit data structure
3. Let be , which is the length of the binary representation of any position in the range . Since any position can be expressed as the sum of at most powers of , the tree has no more than levels. In fact, the number of levels is either or , depending on the value of (theory_TODO, not clear)

Now, let’s delve into the details of how to solve our sum and add queries on a Fenwick tree.

The following is a minimal implementation.
While we’ve transitioned to 0-based indexing for queries, internally, we still use the 1-based indexing to maintain consistency with the examples above.

#[derive(Debug)]
pub struct FenwickTree {
    tree: Vec<i64>,
}
impl FenwickTree {
    pub fn with_len(n: usize) -> Self {
        Self {
            tree: vec![0; n + 1],
        }
    }
    pub fn len(&self) -> usize {
        self.tree.len() - 1
    }
    /// Indexing is 0-based, even if internally we use 1-based indexing
    pub fn add(&mut self, i: usize, delta: i64) {
        let mut i = i + 1; 
        assert!(i < self.tree.len());

        while i < self.tree.len() {
            self.tree[i] += delta;
            i = Self::next_sibling(i);
        }
    }
    /// Indexing is 0-based, even if internally we use 1-based indexing
    pub fn sum(&self, i: usize) -> i64 {
        let mut i = i + 1;  

        assert!(i < self.tree.len());
        let mut sum = 0;
        while i != 0 {
            sum += self.tree[i];
            i = Self::parent(i);
        }
        sum
    }
    pub fn range_sum(&self, l: usize, r: usize) -> i64 {
        self.sum(r) - if l == 0 { 0 } else { self.sum(l - 1) }
    }
    fn isolate_trailing_one(i: usize) -> usize {
        if i == 0 {
            0
        } else {
            1 << i.trailing_zeros()
        }
    }
    fn parent(i: usize) -> usize {
        i - Self::isolate_trailing_one(i)
    }
    fn next_sibling(i: usize) -> usize {
        i + Self::isolate_trailing_one(i)
    }
}
Copy

We are given an array A[1,n] initially set to 0.
We want to support two operations:

• access(i) returns A[i]
• range_update(l, r, v), updates the entries in A[l,r] adding to them v

The following Fenwick solution solve the problem on an array B[1,n].

1. from B we build the Fenwick Tree of length n (mind that B is initialized with all zeros)
2. the operation access(i) is a wrapper of the operation sum(i) we have seen before
3. the operation range_update(l,r,v) exploit the operation add(i, v) of the implementation of the Fenwick Tree:
   1. first we check that l is <= than r, aka that the interval of entries to update is well formed
   2. then we check that r <= n, aka that the interval of entries to update is actually in the array
   3. we perform add(l,v): this trigger the addition of the value v to each node whose range include the position l in the Fenwick Tree
   4. we perform add(r, -v): this trigger the subtraction of the value v to each node whose range include the position r in the Fenwick Tree
   5. we have added and subtracted the same same quantity v in the Fenwick tree, this means that prefix sum are coherent and the elements in [l,r] are increased by v

#[derive(Debug)]
struct UpdateArray {
    ft: FenwickTree,
}
impl UpdateArray {
    pub fn with_len(n: usize) -> Self {
        Self {
            ft: FenwickTree::with_len(n),
        }
    }
    pub fn len(&self) -> usize {
        self.ft.len()
    }
    pub fn access(&self, i: usize) -> i64 {
        self.ft.sum(i)
    }
    pub fn range_update(&mut self, l: usize, r: usize, v: i64) {
        assert!(l <= r);
        assert!(r < self.ft.len());

        self.ft.add(l, v);
        if r + 1 < self.ft.len() {
            self.ft.add(r + 1, -v);
        }
    }
}
Copy

We use a sweep line & Fenwick tree approach.

For starters we map the segments to the range and sort them by their starting point.
Then we build the Fenwick tree, we scan each segment and add in each position

Now we scan the segments again.
When we process the segment we observe that the segments already processed are only the ones that starts before the current one, as they are sorted by their starting points.
Now to find the solution of this problem for the current segment (aka the number of segments contained in the current one) we need to know the number of these segments (the ones that starts before the current one) that also end before the current one, before .
This is computed with a query sum(r_i) on the Fenwick Tree.
After computing the solution for the current segment we subtract to position , to remove the contribution of the right endpoint of the current segment.

The following snippet implement the solution above, using the Fenwick tree previously defined.

fn fenwick_nested_segments(input_segments: &[(i32, i32)]) -> Vec<(i64, usize)> {
	let n = input_segments.len();
	// (start, end, index_in_input)
	let mut events: Vec<(i32, i32, usize)> = Vec::with_capacity(n);
	for (i, &(l, r)) in input_segments.iter().enumerate() {
		events.push((l, r, i));
	}
	// sort by starting endpoint
	events.sort_by(|a, b| a.0.cmp(&b.0));
	let mut tree = FenwickTree::with_len(input_segments.len()*2 + 1);
	for i in 0..n {
		tree.add(events[i].1 as usize, 1);
	}
	let mut sol: Vec<(i64, usize)> = Vec::with_capacity(n);
	for i in 0..n {
		sol.push((tree.sum(events[i].1 as usize) - 1, events[i].2));
		tree.add(events[i].1 as usize, -1);
	}
	// restore so that the solution are paired with the input ordering
	sol.sort_by(|a, b| a.1.cmp(&b.1));
	
	sol
}
Copy

A Segment Tree is a data structure that stores information about array intervals as a tree.
This allows answering range queries over an array efficiently, while still being flexible enough to allow quick modification of the array.

The key point here is range queries, not only range sums!
We can find the sum of consecutive array elementsA[l..r] or find the minimum element in a segment in time.
Between answering such queries we can modifying the elements by replacing one element of the array, or even changing the elements of a whole subsegment (e.g., assigning all elements a[l..r] to any value, or adding a value to all element in the subsegment)

Segment trees can be generalized to larger dimensions. For instance, with 2-dimensional Segment trees you can answer sum or minimum queries over some subrectangle of a given matrix in time.

We consider the simplest form of Segment Trees.
We want to answer sum queries efficiently.
The formal definition of our task is the following: given an array , the Segment Tree must be able to perform the following operations in time

1. find the sum of elements between the indices and :
2. change values of elements in the array:

Observation: even our simple form of Segment Tree is an improvement over the simpler approaches:

• a naive implementation that uses just the array can update element in but requires to compute each sum query
• a precomputed prefix sums can compute the sum queries in but updating an array element requires changes to the prefix sums

Let's now solve nested segments with a Segment Tree and Sweep Line

Given the input array segments we compute the maximum endpoint between the segments, and call it n.
Then we create a segment tree, based on an array of length , initialized with all zeroes.
At this point we create the array axis, which stores triples where:

• the first element of the triple is a segment endpoint
• the second element is the index of the endpoint's segment in segments
• the third element is a boolean isStart, which is set to true if the endpoint is the start of its segment, otherwise the end.

We sort axis by the first element, the segments endpoints.
Finally we "sweep" over axis.

• for `i = 0 to axis.length()
  • if axis[i].isStart == false, aka if the current endpoint is the end of its segment
    • the number of nested segments in the segment where axis[i].endpoint, that we call res, is the range sum on the range [segments[axis[i].index, axis[i].endpoint
    • we push the tuple (axis[i].index, res) in the array of results
    • we increase by one the start of the segment indexed with axis[i].index in segments
  • sort results by the indexes and return it

Why it works?


In words:
Consider the segments .

When we find the end of a segment , namely we do the range sum of to get the number of segments contained in the segment .
Then we increase by the segment in the segment tree.

This works because we increase by one the start when its segment has been closed.
The range sum on will count only segments that starts after and have already been closed (otherwise they would be in the tree).

Alternatively said:

• find the end of the segment , .
• do the range sum
  • all the segments that starts after and have already been closed have caused the increment by one of
    • starts after and already been closed, fully contained in
• the segment has been closed, increase by one in the tree.

The Mo’s Algorithm is a powerful and efficient technique for solving a wide variety of range query problems.
It becomes particularly useful for kind of queries where the use of a Segment Tree or similar data structures are not feasible.
This typically occurs when the query is non-associative, meaning that the result of a query on a range cannot be derived by combining the answers of the subranges that cover the original range.

Mo’s algorithm typically achieves a time complexity of , where represents the size of the dataset, and is the number of queries.

Let's consider an easier problem than Powerful Array
We are given an array consisting of colors, with each color represented by an integer within .
Additionally we are given a set of range queries called three_or_more.
The query three_or_more(l,r) aims to count the colors that occur at least three times in the subarray .

A straightforward solution for the problem: simply scan the subarray and use an additional array as a counter to keep track of occurrences of each color within the range.
Whenever a color reaches three the answer is incremented by 1.
Mind that after each query we have to reset the array of counters.

Indeed, it’s evident that it has a time complexity of .
The figure below illustrates an input that showcases the worst-case running time.
We have  queries. The first query range has a length of  and spans the entire array. Then, the subsequent query ranges are each one unit shorter, until the last one, which has a length of one.
The total length of these ranges is , which is also the time complexity of the solution.

Let's now see the solution using the Mo's Algorithm.
Suppose we have just answered the query for the range and are now addressing the range .
Instead of starting from scratch, we can update the previous answer and counters by adding or removing the contributions of colors that are new in the query range but not in the previous one, or vice versa.
Specifically, for left endpoints, we must remove all the colors in if , or we need to add all the colors in if . The same applies to right endpoints and .

The rust implementation below uses two closures, add and remove to keep answer and counters updated as we adjust the endpoints

pub fn three_or_more(a: &[usize], queries: &[(usize, usize)]) -> Vec<usize> {
    let mut counters: Vec<usize> = vec![0; a.len()];
    let mut answers = Vec::with_capacity(queries.len());

    let mut cur_l = 0;
    let mut cur_r = 0; // here right endpoint is excluded
    let mut answer = 0;

    for &(l, r) in queries {
        let mut add = |i| {
            counters[a[i]] += 1;
            if counters[a[i]] == 3 {
                answer += 1
            }
        };
        
        while cur_l > l {
            cur_l -= 1;
            add(cur_l);
        }
        while cur_r <= r {
            add(cur_r);
            cur_r += 1;
        }
        
        let mut remove = |i| {
            counters[a[i]] -= 1;
            if counters[a[i]] == 2 {
                answer -= 1
            }
        };
        
        while cur_l < l {
            remove(cur_l);
            cur_l += 1;
        }
        while cur_r > r + 1 {
            cur_r -= 1;
            remove(cur_r);
        }
        answers.push(answer);
    }
    answers
}
Copy

The time complexity of the algorithm remains .
However we observe that a query now executes more quickly if its range significantly overlaps with the range of the previous query.

This implementation is highly sensitive to the ordering of the queries.
The previous figure becomes now a best-case for the new implementation as it takes time. Indeed, after spending linear time on the first query, any subsequent query is answered in constant time.
Mind that it is enough to modify the ordering of the above queries to revert to quadratic time (alternate between very short and very long queries).

The above considerations lead to a question: if we have a sufficient number of queries, can we rearrange them in a way that exploits the overlap between successive queries to gain an asymptotic advantage in the overall running time?
Mo's Algorithm answers positively to this question by providing a reordering of the queries such that the time complexity is reduces to

The idea is to conceptually partition the array into buckets, each of size , named .
A query belongs to a bucket if and only if its left endpoint falls into the bucket, which can be expressed as
Initially we group the queries based on their corresponding buckets, and within each bucket the queries are solved in ascending order of their right endpoints.

The figure shows this bucketing approach and the queries of one bucket sorted by their right endpoint.

Let's analyze the complexity of the solution using this ordering
It is sufficient to count the number of times we move the indexes cur_l and cur_r. This is because both add and remove take constant time, and thus the time complexity is proportional to the overall number of moves of these two indexes.

Let's concentrate on a specific bucket. As we process the queries in ascending order of their right endpoints, the index cur_r moves a total of at most times.
On the other hand, the index cur_l can both increase and decrease but it is limited within the bucket, and thus it cannot move more than times per query.
Thus, for a bucket with queries, the overall time to process its queries is .

Summing up over all buckets the time complexity is , aka .

Here's a Rust implementation of the reordering process.
We sort the queries by buckets, using their left endpoints, and within the same bucket we sort them in ascending order by their right endpoints.
We also have to compute a permutation to keep track of how the queries have been reordered. This permutation is essential for returning the answers to their original ordering.

pub fn mos(a: &[usize], queries: &[(usize, usize)]) -> Vec<usize> {
    // Sort the queries by bucket, get the permutation induced by this sorting.
    // The latter is needed to permute the answers to the original ordering
    let mut sorted_queries: Vec<_> = queries.iter().cloned().collect();
	    let mut permutation: Vec<usize> = (0..queries.len()).collect();

    let sqrt_n = (a.len() as f64) as usize + 1;
    sorted_queries.sort_by_key(|&(l, r)| (l / sqrt_n, r));
    permutation.sort_by_key(|&i| (queries[i].0 / sqrt_n, queries[i].1));

    let answers = three_or_more(a, &sorted_queries);

    let mut permuted_answers = vec![0; answers.len()];
    for (i, answer) in permutation.into_iter().zip(answers) {
        permuted_answers[i] = answer;
    }

    permuted_answers
}
Copy

Final Considerations on Mo's Algorithm
Mo’s algorithm is an offline approach, which means we cannot use it when we are constrained to a specific order of queries or when update operations are involved.

When implementing Mo’s algorithm, the most challenging aspect is implementing the functions add and remove.
There are query types for which these operations are not as straightforward as in previous problems and require the use of more advanced data structures than just an array of counters

We can just use Mo's Algorithm and a little bit of attention in updating the answer after a add or a remove.

The solution is identical to the one seen in the previous problem, with one difference.
We are not interested anymore in the number of occurrences of , denoted , in a given subarray, but we want to compute When we increase the number of an occurrence we have to first remove the number obtained when we thought that there was one less occurrence.
Code talks more than words:

let mut add = |i| {
	// we found another occurrence of i, we remove the old "power"
	sum -= counters[a[i]] * counters[a[i]] * a[i];
	counters[a[i]] += 1;
	// we update the power using the right number of occurreces of i
	sum += counters[a[i]] * counters[a[i]] * a[i];
};

let mut remove = |i| {
	sum -= counters[a[i]] * counters[a[i]] * a[i];
	counters[a[i]] -= 1;
	sum += counters[a[i]] * counters[a[i]] * a[i];
};
Copy